In modern 2D computer graphics, the term “stroking” is the process of generating and painting an outline of a path to create the visual effect of dragging a pen along the path. The pen has a user-defined width, often referred to as the pre-determined stroke-width, and a colour fill.
A path can be formed by a plurality of connecting segments of two types, namely line segments and curve segments. A line segment is a straight line with a user-defined start point and a user-defined end point, and is easy to stroke, as the stroke is simply a rectangular area. On the other hand, a curve segment is a lot more complex. The curve segment defines a non-linear movement from a start point to an end point. Depending on the graphic standard, a curve segment is representable using different mathematical forms. For example, the 2D Graphic Standard OpenVG allows users to define a curve segment using a quadratic Bézier curve, a cubic Bézier curve or an elliptical arc. Several approaches have been attempted to correctly render a stroked curve segment.
One brute-force approach is to approximate the area covered by the stroke using a set of quadrilaterals. Each quadrilateral is generated based on a pair of normal lines centred on the curve segment, and added as a separate polygon. This approach produces accurate stroked output, however this is achieved at the expense of speed performance, as excessive straight-line edges are processed from all the quadrilaterals.
Another approach is to generate a left and a right offset path from the curve segment, sometimes referred to as the centreline curve. The offset path is defined by a series of points offset from the curve segment with a distance of half of the stroke-width. This is achieved by first generating a plurality of points along the curve segment, and then projecting the points out to the left and the right from the centreline curve by half of the stroke-width. Although the exact technique used for projecting the points varies from implementation to implementation, the common method is to project along the corresponding normal line of the centreline curve.
FIG. 3 depicts an example of stroking a curve segment 380 using the offset path approach (this being referred to as the “offset stroking method”), where a final stroke polygon is represented by the solid black lines. The points on the curve 380 are generated in the order from 340 to 350 and are represented by solid black dots. Each point is projected along its corresponding normal line, which is represented by the dashed line, to generate a left offset path (301 to 314) and a right offset path (321 to 334). Lines 360 and 365 are also added as butt end caps to complete the stroke polygon. When the final stroke polygon is filled with the user-defined stroke colour, the filling is performed using the “non-zero winding rule” to cover the entire stroked area. The non-zero winding rule is described hereinafter in more detail with reference to FIG. 7.
However, the offset stroking method, which has the advantage of greater speed, has a problem in that it can produce incorrect output, due to unfilled regions. This incorrect output occurs when stroking certain curves with high curvature and large stroke width.